/*
 * @lc app=leetcode.cn id=53 lang=cpp
 *
 * [53] 最大子数组和
 */
c++#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    //动态规划
    int maxSubArray(vector<int>& nums) {
        //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
        int result = INT_MIN;
        int numsSize = int(nums.size());
        //dp[i]表示nums中以nums[i]结尾的最大子序和
        vector<int> dp(numsSize);
        dp[0] = nums[0];
        result = dp[0];
        for (int i = 1; i < numsSize; i++)
        {
            //dp[i]表示以i为结尾的最大子序列和
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(result, dp[i]);
        }

        return result;
    }
};
// @lc code=end

/**
 * 暴力法超时
 *  int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {
            return 0;
        }
        if( n == 1) {
            return nums[0];
        }
        int fast = 0;int slow = 0;
        int ans = nums[0];
        int max = 0;
        //优化指针
        int flag = 0;
        while(fast < n) {
            //慢指针跟上
            if(ans < 0) {
                flag = fast;
            }
            slow = flag;
            while(slow <= fast) {
                max = 0;
                for(int i = slow;i <= fast;i++) {
                    max += nums[i];
                }
                if(ans < max) {
                    ans = max;
                }
                slow ++;
            }
            fast ++;
        }
        return ans;
    }
 * 
 */

